home *** CD-ROM | disk | FTP | other *** search
/ Amiga Games Extra 1996 September / Amiga Games Extra CD-ROM 9-1996.iso / userbox / publicdomain / vim-4.2 / src / regexp.c < prev    next >
C/C++ Source or Header  |  1996-06-09  |  45KB  |  1,884 lines
  1. /* vi:set ts=4 sw=4:
  2.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  3.  *
  4.  * This is NOT the original regular expression code as written by
  5.  * Henry Spencer. This code has been modified specifically for use
  6.  * with the VIM editor, and should not be used apart from compiling
  7.  * VIM. If you want a good regular expression library, get the
  8.  * original code. The copyright notice that follows is from the
  9.  * original.
  10.  *
  11.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  12.  *
  13.  *
  14.  * vim_regcomp and vim_regexec -- vim_regsub and regerror are elsewhere
  15.  *
  16.  *        Copyright (c) 1986 by University of Toronto.
  17.  *        Written by Henry Spencer.  Not derived from licensed software.
  18.  *
  19.  *        Permission is granted to anyone to use this software for any
  20.  *        purpose on any computer system, and to redistribute it freely,
  21.  *        subject to the following restrictions:
  22.  *
  23.  *        1. The author is not responsible for the consequences of use of
  24.  *                this software, no matter how awful, even if they arise
  25.  *                from defects in it.
  26.  *
  27.  *        2. The origin of this software must not be misrepresented, either
  28.  *                by explicit claim or by omission.
  29.  *
  30.  *        3. Altered versions must be plainly marked as such, and must not
  31.  *                be misrepresented as being the original software.
  32.  *
  33.  * Beware that some of this code is subtly aware of the way operator
  34.  * precedence is structured in regular expressions.  Serious changes in
  35.  * regular-expression syntax might require a total rethink.
  36.  *
  37.  * $Log:        regexp.c,v $
  38.  * Revision 1.2  88/04/28  08:09:45  tony
  39.  * First modification of the regexp library. Added an external variable
  40.  * 'reg_ic' which can be set to indicate that case should be ignored.
  41.  * Added a new parameter to vim_regexec() to indicate that the given string
  42.  * comes from the beginning of a line and is thus eligible to match
  43.  * 'beginning-of-line'.
  44.  *
  45.  * Revisions by Olaf 'Rhialto' Seibert, rhialto@mbfys.kun.nl:
  46.  * Changes for vi: (the semantics of several things were rather different)
  47.  * - Added lexical analyzer, because in vi magicness of characters
  48.  *   is rather difficult, and may change over time.
  49.  * - Added support for \< \> \1-\9 and ~
  50.  * - Left some magic stuff in, but only backslashed: \| \+
  51.  * - * and \+ still work after \) even though they shouldn't.
  52.  */
  53. #include "vim.h"
  54. #include "globals.h"
  55. #include "proto.h"
  56. #undef DEBUG
  57.  
  58. #include <stdio.h>
  59. #include "regexp.h"
  60. #include "option.h"
  61.  
  62. /*
  63.  * The "internal use only" fields in regexp.h are present to pass info from
  64.  * compile to execute that permits the execute phase to run lots faster on
  65.  * simple cases.  They are:
  66.  *
  67.  * regstart     char that must begin a match; '\0' if none obvious
  68.  * reganch        is the match anchored (at beginning-of-line only)?
  69.  * regmust        string (pointer into program) that match must include, or NULL
  70.  * regmlen        length of regmust string
  71.  *
  72.  * Regstart and reganch permit very fast decisions on suitable starting points
  73.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  74.  * of lines that cannot possibly match.  The regmust tests are costly enough
  75.  * that vim_regcomp() supplies a regmust only if the r.e. contains something
  76.  * potentially expensive (at present, the only such thing detected is * or +
  77.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  78.  * supplied because the test in vim_regexec() needs it and vim_regcomp() is
  79.  * computing it anyway.
  80.  */
  81.  
  82. /*
  83.  * Structure for regexp "program".    This is essentially a linear encoding
  84.  * of a nondeterministic finite-state machine (aka syntax charts or
  85.  * "railroad normal form" in parsing technology).  Each node is an opcode
  86.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  87.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  88.  * a BRANCH on both ends of it is connecting two alternatives.    (Here we
  89.  * have one of the subtle syntax dependencies:    an individual BRANCH (as
  90.  * opposed to a collection of them) is never concatenated with anything
  91.  * because of operator precedence.)  The operand of some types of node is
  92.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  93.  * particular, the operand of a BRANCH node is the first node of the branch.
  94.  * (NB this is *not* a tree structure:    the tail of the branch connects
  95.  * to the thing following the set of BRANCHes.)  The opcodes are:
  96.  */
  97.  
  98. /* definition    number               opnd?    meaning */
  99. #define END     0                /* no    End of program. */
  100. #define BOL     1                /* no    Match "" at beginning of line. */
  101. #define EOL     2                /* no    Match "" at end of line. */
  102. #define ANY     3                /* no    Match any one character. */
  103. #define ANYOF    4                /* str    Match any character in this string. */
  104. #define ANYBUT    5                /* str    Match any character not in this
  105.                                  *        string. */
  106. #define BRANCH    6                /* node Match this alternative, or the
  107.                                  *        next... */
  108. #define BACK    7                /* no    Match "", "next" ptr points backward. */
  109. #define EXACTLY 8                /* str    Match this string. */
  110. #define NOTHING 9                /* no    Match empty string. */
  111. #define STAR    10                /* node Match this (simple) thing 0 or more
  112.                                  *        times. */
  113. #define PLUS    11                /* node Match this (simple) thing 1 or more
  114.                                  *        times. */
  115. #define BOW        12                /* no    Match "" after [^a-zA-Z0-9_] */
  116. #define EOW        13                /* no    Match "" at    [^a-zA-Z0-9_] */
  117. #define IDENT    14                /* no    Match identifier char */
  118. #define WORD    15                /* no    Match keyword char */
  119. #define FNAME   16                /* no    Match file name char */
  120. #define PRINT    17                /* no    Match printable char */
  121. #define SIDENT    18                /* no    Match identifier char but no digit */
  122. #define SWORD    19                /* no    Match word char but no digit */
  123. #define SFNAME    20                /* no    Match file name char but no digit */
  124. #define SPRINT    21                /* no    Match printable char but no digit */
  125. #define MOPEN    30                /* no    Mark this point in input as start of
  126.                                  *        #n. */
  127.  /* MOPEN+1 is number 1, etc. */
  128. #define MCLOSE    40                /* no    Analogous to MOPEN. */
  129. #define BACKREF    50                /* node Match same string again \1-\9 */
  130.  
  131. #define Magic(x)    ((x)|('\\'<<8))
  132.  
  133. /*
  134.  * Opcode notes:
  135.  *
  136.  * BRANCH        The set of branches constituting a single choice are hooked
  137.  *                together with their "next" pointers, since precedence prevents
  138.  *                anything being concatenated to any individual branch.  The
  139.  *                "next" pointer of the last BRANCH in a choice points to the
  140.  *                thing following the whole choice.  This is also where the
  141.  *                final "next" pointer of each individual branch points; each
  142.  *                branch starts with the operand node of a BRANCH node.
  143.  *
  144.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  145.  *                exists to make loop structures possible.
  146.  *
  147.  * STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
  148.  *                BRANCH structures using BACK.  Simple cases (one character
  149.  *                per match) are implemented with STAR and PLUS for speed
  150.  *                and to minimize recursive plunges.
  151.  *                Note: We would like to use "\?" instead of "\=", but a "\?"
  152.  *                can be part of a pattern to escape the special meaning of '?'
  153.  *                at the end of the pattern in "?pattern?e".
  154.  *
  155.  * MOPEN,MCLOSE    ...are numbered at compile time.
  156.  */
  157.  
  158. /*
  159.  * A node is one char of opcode followed by two chars of "next" pointer.
  160.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  161.  * value is a positive offset from the opcode of the node containing it.
  162.  * An operand, if any, simply follows the node.  (Note that much of the
  163.  * code generation knows about this implicit relationship.)
  164.  *
  165.  * Using two bytes for the "next" pointer is vast overkill for most things,
  166.  * but allows patterns to get big without disasters.
  167.  */
  168. #define OP(p)    (*(p))
  169. #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  170. #define OPERAND(p)        ((p) + 3)
  171.  
  172. /*
  173.  * Utility definitions.
  174.  */
  175. #ifndef CHARBITS
  176. #define UCHARAT(p)        ((int)*(unsigned char *)(p))
  177. #else
  178. #define UCHARAT(p)        ((int)*(p)&CHARBITS)
  179. #endif
  180.  
  181. #define EMSG_RETURN(m) { emsg(m); rc_did_emsg = TRUE; return NULL; }
  182.  
  183. static int ismult __ARGS((int));
  184. static char_u *cstrchr __ARGS((char_u *, int));
  185.  
  186.     static int
  187. ismult(c)
  188.     int c;
  189. {
  190.     return (c == Magic('*') || c == Magic('+') || c == Magic('='));
  191. }
  192.  
  193. /*
  194.  * Flags to be passed up and down.
  195.  */
  196. #define HASWIDTH        01        /* Known never to match null string. */
  197. #define SIMPLE            02        /* Simple enough to be STAR/PLUS operand. */
  198. #define SPSTART         04        /* Starts with * or +. */
  199. #define WORST            0        /* Worst case. */
  200.  
  201. /*
  202.  * The following allows empty REs, meaning "the same as the previous RE".
  203.  * per the ed(1) manual.
  204.  */
  205. /* #define EMPTY_RE */            /* this is done outside of regexp */
  206. #ifdef EMPTY_RE
  207. char_u           *reg_prev_re;
  208. #endif
  209.  
  210. #define TILDE
  211. #ifdef TILDE
  212. char_u           *reg_prev_sub;
  213. #endif
  214.  
  215. /*
  216.  * Global work variables for vim_regcomp().
  217.  */
  218.  
  219. static char_u    *regparse;    /* Input-scan pointer. */
  220. static int        regnpar;        /* () count. */
  221. static char_u     regdummy;
  222. static char_u   *regcode;        /* Code-emit pointer; ®dummy = don't. */
  223. static long     regsize;        /* Code size. */
  224. static char_u   **regendp;        /* Ditto for endp. */
  225.  
  226. /*
  227.  * META contains all characters that may be magic, except '^' and '$'.
  228.  * This depends on the configuration options TILDE, BACKREF.
  229.  * (could be done simpler for compilers that know string concatenation)
  230.  */
  231.  
  232. #ifdef TILDE
  233. # ifdef BACKREF
  234.        static char_u META[] = ".[()|=+*<>iIkKfFpP~123456789";
  235. # else
  236.        static char_u META[] = ".[()|=+*<>iIkKfFpP~";
  237. # endif
  238. #else
  239. # ifdef BACKREF
  240.        static char_u META[] = ".[()|=+*<>iIkKfFpP123456789";
  241. # else
  242.        static char_u META[] = ".[()|=+*<>iIkKfFpP";
  243. # endif
  244. #endif
  245.  
  246. /*
  247.  * REGEXP_ABBR contains all characters which act as abbreviations after '\'.
  248.  * These are:
  249.  *    \r    - New line (CR).
  250.  *    \t    - Tab (TAB).
  251.  *    \e    - Escape (ESC).
  252.  *    \b    - Backspace (Ctrl('H')).
  253.  */
  254. static char_u REGEXP_ABBR[] = "rteb";
  255.  
  256. /*
  257.  * Forward declarations for vim_regcomp()'s friends.
  258.  */
  259. static void        initchr __ARGS((char_u *));
  260. static int        getchr __ARGS((void));
  261. static int        peekchr __ARGS((void));
  262. #define PeekChr() curchr    /* shortcut only when last action was peekchr() */
  263. static int         curchr;
  264. static void        skipchr __ARGS((void));
  265. static void        ungetchr __ARGS((void));
  266. static char_u    *reg __ARGS((int, int *));
  267. static char_u    *regbranch __ARGS((int *));
  268. static char_u    *regpiece __ARGS((int *));
  269. static char_u    *regatom __ARGS((int *));
  270. static char_u    *regnode __ARGS((int));
  271. static char_u    *regnext __ARGS((char_u *));
  272. static void     regc __ARGS((int));
  273. static void     unregc __ARGS((void));
  274. static void     reginsert __ARGS((int, char_u *));
  275. static void     regtail __ARGS((char_u *, char_u *));
  276. static void     regoptail __ARGS((char_u *, char_u *));
  277.  
  278. #ifndef HAVE_STRCSPN
  279. static size_t    strcspn __ARGS((const char_u *, const char_u *));
  280. #endif
  281.  
  282. /*
  283.  * skip past regular expression
  284.  * stop at end of 'p' of where 'dirc' is found ('/', '?', etc)
  285.  * take care of characters with a backslash in front of it
  286.  * skip strings inside [ and ].
  287.  */
  288.     char_u *
  289. skip_regexp(p, dirc)
  290.     char_u    *p;
  291.     int        dirc;
  292. {
  293.     int        in_range = FALSE;
  294.  
  295.     for (; p[0] != NUL; ++p)
  296.     {
  297.         if (p[0] == dirc && !in_range)        /* found end of regexp */
  298.             break;
  299.         if ((p[0] == '[' && p_magic) || (p[0] == '\\' && p[1] == '[' && !p_magic))
  300.         {
  301.             in_range = TRUE;
  302.             if (p[0] == '\\')
  303.                 ++p;
  304.                                 /* "[^]" and "[]" are not the end of a range */
  305.             if (p[1] == '^')
  306.                 ++p;
  307.             if (p[1] == ']')
  308.                 ++p;
  309.         }
  310.         else if (p[0] == '\\' && p[1] != NUL)
  311.             ++p;    /* skip next character */
  312.         else if (p[0] == ']')
  313.             in_range = FALSE;
  314.     }
  315.     return p;
  316. }
  317.  
  318. /*
  319.  - vim_regcomp - compile a regular expression into internal code
  320.  *
  321.  * We can't allocate space until we know how big the compiled form will be,
  322.  * but we can't compile it (and thus know how big it is) until we've got a
  323.  * place to put the code.  So we cheat:  we compile it twice, once with code
  324.  * generation turned off and size counting turned on, and once "for real".
  325.  * This also means that we don't allocate space until we are sure that the
  326.  * thing really will compile successfully, and we never have to move the
  327.  * code and thus invalidate pointers into it.  (Note that it has to be in
  328.  * one piece because vim_free() must be able to free it all.)
  329.  *
  330.  * Beware that the optimization-preparation code in here knows about some
  331.  * of the structure of the compiled regexp.
  332.  */
  333.     regexp           *
  334. vim_regcomp(exp)
  335.     char_u           *exp;
  336. {
  337.     register regexp *r;
  338.     register char_u  *scan;
  339.     register char_u  *longest;
  340.     register int    len;
  341.     int             flags;
  342. /*    extern char    *malloc();*/
  343.  
  344.     if (exp == NULL)
  345.         EMSG_RETURN(e_null);
  346.  
  347. #ifdef EMPTY_RE            /* this is done outside of regexp */
  348.     if (*exp == '\0')
  349.     {
  350.         if (reg_prev_re)
  351.             exp = reg_prev_re;
  352.         else
  353.             EMSG_RETURN(e_noprevre);
  354.     }
  355. #endif
  356.  
  357.     /* First pass: determine size, legality. */
  358.     initchr((char_u *)exp);
  359.     regnpar = 1;
  360.     regsize = 0L;
  361.     regcode = ®dummy;
  362.     regendp = NULL;
  363.     regc(MAGIC);
  364.     if (reg(0, &flags) == NULL)
  365.         return NULL;
  366.  
  367.     /* Small enough for pointer-storage convention? */
  368.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  369.         EMSG_RETURN(e_toolong);
  370.  
  371.     /* Allocate space. */
  372. /*    r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
  373.     r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
  374.     if (r == NULL)
  375.         return NULL;
  376.  
  377. #ifdef EMPTY_RE            /* this is done outside of regexp */
  378.     if (exp != reg_prev_re) {
  379.         vim_free(reg_prev_re);
  380.         if (reg_prev_re = alloc(STRLEN(exp) + 1))
  381.             STRCPY(reg_prev_re, exp);
  382.     }
  383. #endif
  384.  
  385.     /* Second pass: emit code. */
  386.     initchr((char_u *)exp);
  387.     regnpar = 1;
  388.     regcode = r->program;
  389.     regendp = r->endp;
  390.     regc(MAGIC);
  391.     if (reg(0, &flags) == NULL) {
  392.         vim_free(r);
  393.         return NULL;
  394.     }
  395.  
  396.     /* Dig out information for optimizations. */
  397.     r->regstart = '\0';         /* Worst-case defaults. */
  398.     r->reganch = 0;
  399.     r->regmust = NULL;
  400.     r->regmlen = 0;
  401.     scan = r->program + 1;        /* First BRANCH. */
  402.     if (OP(regnext(scan)) == END) {     /* Only one top-level choice. */
  403.         scan = OPERAND(scan);
  404.  
  405.         /* Starting-point info. */
  406.         if (OP(scan) == EXACTLY)
  407.             r->regstart = *OPERAND(scan);
  408.         else if (OP(scan) == BOL)
  409.             r->reganch++;
  410.  
  411.         /*
  412.          * If there's something expensive in the r.e., find the longest
  413.          * literal string that must appear and make it the regmust.  Resolve
  414.          * ties in favor of later strings, since the regstart check works
  415.          * with the beginning of the r.e. and avoiding duplication
  416.          * strengthens checking.  Not a strong reason, but sufficient in the
  417.          * absence of others.
  418.          */
  419.         /*
  420.          * When the r.e. starts with BOW, it is faster to look for a regmust
  421.          * first. Used a lot for "#" and "*" commands. (Added by mool).
  422.          */
  423.         if (flags & SPSTART || OP(scan) == BOW) {
  424.             longest = NULL;
  425.             len = 0;
  426.             for (; scan != NULL; scan = regnext(scan))
  427.                 if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len) {
  428.                     longest = OPERAND(scan);
  429.                     len = STRLEN(OPERAND(scan));
  430.                 }
  431.             r->regmust = longest;
  432.             r->regmlen = len;
  433.         }
  434.     }
  435. #ifdef DEBUG
  436.     regdump(r);
  437. #endif
  438.     return r;
  439. }
  440.  
  441. /*
  442.  - reg - regular expression, i.e. main body or parenthesized thing
  443.  *
  444.  * Caller must absorb opening parenthesis.
  445.  *
  446.  * Combining parenthesis handling with the base level of regular expression
  447.  * is a trifle forced, but the need to tie the tails of the branches to what
  448.  * follows makes it hard to avoid.
  449.  */
  450.     static char_u *
  451. reg(paren, flagp)
  452.     int             paren;        /* Parenthesized? */
  453.     int            *flagp;
  454. {
  455.     register char_u  *ret;
  456.     register char_u  *br;
  457.     register char_u  *ender;
  458.     register int    parno = 0;
  459.     int             flags;
  460.  
  461.     *flagp = HASWIDTH;            /* Tentatively. */
  462.  
  463.     /* Make an MOPEN node, if parenthesized. */
  464.     if (paren) {
  465.         if (regnpar >= NSUBEXP)
  466.             EMSG_RETURN(e_toombra);
  467.         parno = regnpar;
  468.         regnpar++;
  469.         ret = regnode(MOPEN + parno);
  470.         if (regendp)
  471.             regendp[parno] = NULL;    /* haven't seen the close paren yet */
  472.     } else
  473.         ret = NULL;
  474.  
  475.     /* Pick up the branches, linking them together. */
  476.     br = regbranch(&flags);
  477.     if (br == NULL)
  478.         return NULL;
  479.     if (ret != NULL)
  480.         regtail(ret, br);        /* MOPEN -> first. */
  481.     else
  482.         ret = br;
  483.     if (!(flags & HASWIDTH))
  484.         *flagp &= ~HASWIDTH;
  485.     *flagp |= flags & SPSTART;
  486.     while (peekchr() == Magic('|')) {
  487.         skipchr();
  488.         br = regbranch(&flags);
  489.         if (br == NULL)
  490.             return NULL;
  491.         regtail(ret, br);        /* BRANCH -> BRANCH. */
  492.         if (!(flags & HASWIDTH))
  493.             *flagp &= ~HASWIDTH;
  494.         *flagp |= flags & SPSTART;
  495.     }
  496.  
  497.     /* Make a closing node, and hook it on the end. */
  498.     ender = regnode((paren) ? MCLOSE + parno : END);
  499.     regtail(ret, ender);
  500.  
  501.     /* Hook the tails of the branches to the closing node. */
  502.     for (br = ret; br != NULL; br = regnext(br))
  503.         regoptail(br, ender);
  504.  
  505.     /* Check for proper termination. */
  506.     if (paren && getchr() != Magic(')'))
  507.         EMSG_RETURN(e_toombra)
  508.     else if (!paren && peekchr() != '\0')
  509.     {
  510.         if (PeekChr() == Magic(')'))
  511.             EMSG_RETURN(e_toomket)
  512.         else
  513.             EMSG_RETURN(e_trailing)        /* "Can't happen". */
  514.         /* NOTREACHED */
  515.     }
  516.     /*
  517.      * Here we set the flag allowing back references to this set of
  518.      * parentheses.
  519.      */
  520.     if (paren && regendp)
  521.         regendp[parno] = ender;    /* have seen the close paren */
  522.     return ret;
  523. }
  524.  
  525. /*
  526.  - regbranch - one alternative of an | operator
  527.  *
  528.  * Implements the concatenation operator.
  529.  */
  530.     static char_u    *
  531. regbranch(flagp)
  532.     int            *flagp;
  533. {
  534.     register char_u  *ret;
  535.     register char_u  *chain;
  536.     register char_u  *latest;
  537.     int             flags;
  538.  
  539.     *flagp = WORST;             /* Tentatively. */
  540.  
  541.     ret = regnode(BRANCH);
  542.     chain = NULL;
  543.     while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) {
  544.         latest = regpiece(&flags);
  545.         if (latest == NULL)
  546.             return NULL;
  547.         *flagp |= flags & HASWIDTH;
  548.         if (chain == NULL)        /* First piece. */
  549.             *flagp |= flags & SPSTART;
  550.         else
  551.             regtail(chain, latest);
  552.         chain = latest;
  553.     }
  554.     if (chain == NULL)            /* Loop ran zero times. */
  555.         (void) regnode(NOTHING);
  556.  
  557.     return ret;
  558. }
  559.  
  560. /*
  561.  - regpiece - something followed by possible [*+=]
  562.  *
  563.  * Note that the branching code sequences used for = and the general cases
  564.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  565.  * both the endmarker for their branch list and the body of the last branch.
  566.  * It might seem that this node could be dispensed with entirely, but the
  567.  * endmarker role is not redundant.
  568.  */
  569. static char_u    *
  570. regpiece(flagp)
  571.     int            *flagp;
  572. {
  573.     register char_u  *ret;
  574.     register int    op;
  575.     register char_u  *next;
  576.     int             flags;
  577.  
  578.     ret = regatom(&flags);
  579.     if (ret == NULL)
  580.         return NULL;
  581.  
  582.     op = peekchr();
  583.     if (!ismult(op)) {
  584.         *flagp = flags;
  585.         return ret;
  586.     }
  587.     if (!(flags & HASWIDTH) && op != Magic('='))
  588.         EMSG_RETURN((char_u *)"*+ operand could be empty");
  589.     *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH);
  590.  
  591.     if (op == Magic('*') && (flags & SIMPLE))
  592.         reginsert(STAR, ret);
  593.     else if (op == Magic('*')) {
  594.         /* Emit x* as (x&|), where & means "self". */
  595.         reginsert(BRANCH, ret); /* Either x */
  596.         regoptail(ret, regnode(BACK));    /* and loop */
  597.         regoptail(ret, ret);    /* back */
  598.         regtail(ret, regnode(BRANCH));    /* or */
  599.         regtail(ret, regnode(NOTHING)); /* null. */
  600.     } else if (op == Magic('+') && (flags & SIMPLE))
  601.         reginsert(PLUS, ret);
  602.     else if (op == Magic('+')) {
  603.         /* Emit x+ as x(&|), where & means "self". */
  604.         next = regnode(BRANCH); /* Either */
  605.         regtail(ret, next);
  606.         regtail(regnode(BACK), ret);    /* loop back */
  607.         regtail(next, regnode(BRANCH)); /* or */
  608.         regtail(ret, regnode(NOTHING)); /* null. */
  609.     } else if (op == Magic('=')) {
  610.         /* Emit x= as (x|) */
  611.         reginsert(BRANCH, ret); /* Either x */
  612.         regtail(ret, regnode(BRANCH));    /* or */
  613.         next = regnode(NOTHING);/* null. */
  614.         regtail(ret, next);
  615.         regoptail(ret, next);
  616.     }
  617.     skipchr();
  618.     if (ismult(peekchr()))
  619.         EMSG_RETURN((char_u *)"Nested *=+");
  620.  
  621.     return ret;
  622. }
  623.  
  624. /*
  625.  - regatom - the lowest level
  626.  *
  627.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  628.  * it can turn them into a single node, which is smaller to store and
  629.  * faster to run.
  630.  */
  631. static char_u    *
  632. regatom(flagp)
  633.     int            *flagp;
  634. {
  635.     register char_u  *ret;
  636.     int             flags;
  637.  
  638.     *flagp = WORST;             /* Tentatively. */
  639.  
  640.     switch (getchr()) {
  641.       case Magic('^'):
  642.         ret = regnode(BOL);
  643.         break;
  644.       case Magic('$'):
  645.         ret = regnode(EOL);
  646.         break;
  647.       case Magic('<'):
  648.         ret = regnode(BOW);
  649.         break;
  650.       case Magic('>'):
  651.         ret = regnode(EOW);
  652.         break;
  653.       case Magic('.'):
  654.         ret = regnode(ANY);
  655.         *flagp |= HASWIDTH | SIMPLE;
  656.         break;
  657.       case Magic('i'):
  658.           ret = regnode(IDENT);
  659.         *flagp |= HASWIDTH | SIMPLE;
  660.         break;
  661.       case Magic('k'):
  662.           ret = regnode(WORD);
  663.         *flagp |= HASWIDTH | SIMPLE;
  664.         break;
  665.       case Magic('I'):
  666.           ret = regnode(SIDENT);
  667.         *flagp |= HASWIDTH | SIMPLE;
  668.         break;
  669.       case Magic('K'):
  670.           ret = regnode(SWORD);
  671.         *flagp |= HASWIDTH | SIMPLE;
  672.         break;
  673.       case Magic('f'):
  674.           ret = regnode(FNAME);
  675.         *flagp |= HASWIDTH | SIMPLE;
  676.         break;
  677.       case Magic('F'):
  678.           ret = regnode(SFNAME);
  679.         *flagp |= HASWIDTH | SIMPLE;
  680.         break;
  681.       case Magic('p'):
  682.           ret = regnode(PRINT);
  683.         *flagp |= HASWIDTH | SIMPLE;
  684.         break;
  685.       case Magic('P'):
  686.           ret = regnode(SPRINT);
  687.         *flagp |= HASWIDTH | SIMPLE;
  688.         break;
  689.       case Magic('('):
  690.         ret = reg(1, &flags);
  691.         if (ret == NULL)
  692.             return NULL;
  693.         *flagp |= flags & (HASWIDTH | SPSTART);
  694.         break;
  695.       case '\0':
  696.       case Magic('|'):
  697.       case Magic(')'):
  698.         EMSG_RETURN(e_internal)        /* Supposed to be caught earlier. */
  699.         /* NOTREACHED */
  700.       case Magic('='):
  701.         EMSG_RETURN((char_u *)"\\= follows nothing")
  702.         /* NOTREACHED */
  703.       case Magic('+'):
  704.         EMSG_RETURN((char_u *)"\\+ follows nothing")
  705.         /* NOTREACHED */
  706.       case Magic('*'):
  707.         if (reg_magic)
  708.             EMSG_RETURN((char_u *)"* follows nothing")
  709.         else
  710.             EMSG_RETURN((char_u *)"\\* follows nothing")
  711.         /* break; Not Reached */
  712. #ifdef TILDE
  713.       case Magic('~'):            /* previous substitute pattern */
  714.             if (reg_prev_sub) {
  715.                 register char_u *p;
  716.  
  717.                 ret = regnode(EXACTLY);
  718.                 p = reg_prev_sub;
  719.                 while (*p) {
  720.                     regc(*p++);
  721.                 }
  722.                 regc('\0');
  723.                 if (p - reg_prev_sub) {
  724.                     *flagp |= HASWIDTH;
  725.                     if ((p - reg_prev_sub) == 1)
  726.                         *flagp |= SIMPLE;
  727.                 }
  728.               } else
  729.                 EMSG_RETURN(e_nopresub);
  730.             break;
  731. #endif
  732. #ifdef BACKREF
  733.       case Magic('1'):
  734.       case Magic('2'):
  735.       case Magic('3'):
  736.       case Magic('4'):
  737.       case Magic('5'):
  738.       case Magic('6'):
  739.       case Magic('7'):
  740.       case Magic('8'):
  741.       case Magic('9'): {
  742.             int                refnum;
  743.  
  744.             ungetchr();
  745.             refnum = getchr() - Magic('0');
  746.             /*
  747.              * Check if the back reference is legal. We use the parentheses
  748.              * pointers to mark encountered close parentheses, but this
  749.              * is only available in the second pass. Checking opens is
  750.              * always possible.
  751.              * Should also check that we don't refer to something that
  752.              * is repeated (+*=): what instance of the repetition should
  753.              * we match? TODO.
  754.              */
  755.             if (refnum < regnpar &&
  756.                 (regendp == NULL || regendp[refnum] != NULL))
  757.                 ret = regnode(BACKREF + refnum);
  758.             else
  759.                 EMSG_RETURN((char_u *)"Illegal back reference");
  760.         }
  761.         break;
  762. #endif
  763.       case Magic('['):
  764.         {
  765.             char_u         *p;
  766.  
  767.             /*
  768.              * If there is no matching ']', we assume the '[' is a normal
  769.              * character. This makes ":help [" work.
  770.              */
  771.             p = regparse;
  772.             if (*p == '^')     /* Complement of range. */
  773.                 ++p;
  774.             if (*p == ']' || *p == '-')
  775.                 ++p;
  776.             while (*p != '\0' && *p != ']')
  777.             {
  778.                 if (*p == '-')
  779.                 {
  780.                     ++p;
  781.                     if (*p != ']' && *p != '\0')
  782.                         ++p;
  783.                 }
  784.                 else if (*p == '\\' && p[1] != '\0')
  785.                     p += 2;
  786.                 else
  787.                     ++p;
  788.             }
  789.             if (*p == ']')        /* there is a matching ']' */
  790.             {
  791.                 /*
  792.                  * In a character class, different parsing rules apply.
  793.                  * Not even \ is special anymore, nothing is.
  794.                  */
  795.                 if (*regparse == '^') {     /* Complement of range. */
  796.                     ret = regnode(ANYBUT);
  797.                     regparse++;
  798.                 } else
  799.                     ret = regnode(ANYOF);
  800.                 if (*regparse == ']' || *regparse == '-')
  801.                     regc(*regparse++);
  802.                 while (*regparse != '\0' && *regparse != ']') {
  803.                     if (*regparse == '-') {
  804.                         regparse++;
  805.                         if (*regparse == ']' || *regparse == '\0')
  806.                             regc('-');
  807.                         else {
  808.                             register int    cclass;
  809.                             register int    cclassend;
  810.  
  811.                             cclass = UCHARAT(regparse - 2) + 1;
  812.                             cclassend = UCHARAT(regparse);
  813.                             if (cclass > cclassend + 1)
  814.                                 EMSG_RETURN(e_invrange);
  815.                             for (; cclass <= cclassend; cclass++)
  816.                                 regc(cclass);
  817.                             regparse++;
  818.                         }
  819.                     } else if (*regparse == '\\' && regparse[1]) {
  820.                         regparse++;
  821.                         regc(*regparse++);
  822.                     } else
  823.                         regc(*regparse++);
  824.                 }
  825.                 regc('\0');
  826.                 if (*regparse != ']')
  827.                     EMSG_RETURN(e_toomsbra);
  828.                 skipchr();            /* let's be friends with the lexer again */
  829.                 *flagp |= HASWIDTH | SIMPLE;
  830.                 break;
  831.             }
  832.         }
  833.         /* FALLTHROUGH */
  834.  
  835.       default:
  836.         {
  837.             register int    len;
  838.             int                chr;
  839.  
  840.             ungetchr();
  841.             len = 0;
  842.             ret = regnode(EXACTLY);
  843.             /*
  844.              * Always take at least one character, for '[' without matching
  845.              * ']'.
  846.              */
  847.             while ((chr = peekchr()) != '\0' && (chr < Magic(0) || len == 0))
  848.             {
  849.                 regc(chr);
  850.                 skipchr();
  851.                 len++;
  852.             }
  853. #ifdef DEBUG
  854.             if (len == 0)
  855.                  EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
  856. #endif
  857.             /*
  858.              * If there is a following *, \+ or \= we need the character
  859.              * in front of it as a single character operand
  860.              */
  861.             if (len > 1 && ismult(chr))
  862.             {
  863.                 unregc();            /* Back off of *+= operand */
  864.                 ungetchr();            /* and put it back for next time */
  865.                 --len;
  866.             }
  867.             regc('\0');
  868.             *flagp |= HASWIDTH;
  869.             if (len == 1)
  870.                 *flagp |= SIMPLE;
  871.         }
  872.         break;
  873.     }
  874.  
  875.     return ret;
  876. }
  877.  
  878. /*
  879.  - regnode - emit a node
  880.  */
  881. static char_u    *                /* Location. */
  882. regnode(op)
  883.     int            op;
  884. {
  885.     register char_u  *ret;
  886.     register char_u  *ptr;
  887.  
  888.     ret = regcode;
  889.     if (ret == ®dummy) {
  890.         regsize += 3;
  891.         return ret;
  892.     }
  893.     ptr = ret;
  894.     *ptr++ = op;
  895.     *ptr++ = '\0';                /* Null "next" pointer. */
  896.     *ptr++ = '\0';
  897.     regcode = ptr;
  898.  
  899.     return ret;
  900. }
  901.  
  902. /*
  903.  - regc - emit (if appropriate) a byte of code
  904.  */
  905. static void
  906. regc(b)
  907.     int            b;
  908. {
  909.     if (regcode != ®dummy)
  910.         *regcode++ = b;
  911.     else
  912.         regsize++;
  913. }
  914.  
  915. /*
  916.  - unregc - take back (if appropriate) a byte of code
  917.  */
  918. static void
  919. unregc()
  920. {
  921.     if (regcode != ®dummy)
  922.         regcode--;
  923.     else
  924.         regsize--;
  925. }
  926.  
  927. /*
  928.  - reginsert - insert an operator in front of already-emitted operand
  929.  *
  930.  * Means relocating the operand.
  931.  */
  932. static void
  933. reginsert(op, opnd)
  934.     int            op;
  935.     char_u           *opnd;
  936. {
  937.     register char_u  *src;
  938.     register char_u  *dst;
  939.     register char_u  *place;
  940.  
  941.     if (regcode == ®dummy) {
  942.         regsize += 3;
  943.         return;
  944.     }
  945.     src = regcode;
  946.     regcode += 3;
  947.     dst = regcode;
  948.     while (src > opnd)
  949.         *--dst = *--src;
  950.  
  951.     place = opnd;                /* Op node, where operand used to be. */
  952.     *place++ = op;
  953.     *place++ = '\0';
  954.     *place = '\0';
  955. }
  956.  
  957. /*
  958.  - regtail - set the next-pointer at the end of a node chain
  959.  */
  960. static void
  961. regtail(p, val)
  962.     char_u           *p;
  963.     char_u           *val;
  964. {
  965.     register char_u  *scan;
  966.     register char_u  *temp;
  967.     register int    offset;
  968.  
  969.     if (p == ®dummy)
  970.         return;
  971.  
  972.     /* Find last node. */
  973.     scan = p;
  974.     for (;;) {
  975.         temp = regnext(scan);
  976.         if (temp == NULL)
  977.             break;
  978.         scan = temp;
  979.     }
  980.  
  981.     if (OP(scan) == BACK)
  982.         offset = (int)(scan - val);
  983.     else
  984.         offset = (int)(val - scan);
  985.     *(scan + 1) = (char_u) ((offset >> 8) & 0377);
  986.     *(scan + 2) = (char_u) (offset & 0377);
  987. }
  988.  
  989. /*
  990.  - regoptail - regtail on operand of first argument; nop if operandless
  991.  */
  992. static void
  993. regoptail(p, val)
  994.     char_u           *p;
  995.     char_u           *val;
  996. {
  997.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  998.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  999.         return;
  1000.     regtail(OPERAND(p), val);
  1001. }
  1002.  
  1003. /*
  1004.  - getchr() - get the next character from the pattern. We know about
  1005.  * magic and such, so therefore we need a lexical analyzer.
  1006.  */
  1007.  
  1008. /* static int        curchr; */
  1009. static int        prevchr;
  1010. static int        nextchr;    /* used for ungetchr() */
  1011. /*
  1012.  * Note: prevchr is sometimes -1 when we are not at the start,
  1013.  * eg in /[ ^I]^ the pattern was never found even if it existed, because ^ was
  1014.  * taken to be magic -- webb
  1015.  */
  1016. static int        at_start;    /* True when we are on the first character */
  1017.  
  1018. static void
  1019. initchr(str)
  1020. char_u *str;
  1021. {
  1022.     regparse = str;
  1023.     curchr = prevchr = nextchr = -1;
  1024.     at_start = TRUE;
  1025. }
  1026.  
  1027. static int
  1028. peekchr()
  1029. {
  1030.     if (curchr < 0) {
  1031.         switch (curchr = regparse[0]) {
  1032.         case '.':
  1033.     /*    case '+':*/
  1034.     /*    case '=':*/
  1035.         case '[':
  1036.         case '~':
  1037.             if (reg_magic)
  1038.                 curchr = Magic(curchr);
  1039.             break;
  1040.         case '*':
  1041.             /* * is not magic as the very first character, eg "?*ptr" */
  1042.             if (reg_magic && !at_start)
  1043.                 curchr = Magic('*');
  1044.             break;
  1045.         case '^':
  1046.             /* ^ is only magic as the very first character */
  1047.             if (at_start)
  1048.                 curchr = Magic('^');
  1049.             break;
  1050.         case '$':
  1051.             /* $ is only magic as the very last character and in front of '\|' */
  1052.             if (regparse[1] == NUL || (regparse[1] == '\\' && regparse[2] == '|'))
  1053.                 curchr = Magic('$');
  1054.             break;
  1055.         case '\\':
  1056.             regparse++;
  1057.             if (regparse[0] == NUL)
  1058.                 curchr = '\\';    /* trailing '\' */
  1059.             else if (vim_strchr(META, regparse[0]))
  1060.             {
  1061.                 /*
  1062.                  * META contains everything that may be magic sometimes, except
  1063.                  * ^ and $ ("\^" and "\$" are never magic).
  1064.                  * We now fetch the next character and toggle its magicness.
  1065.                  * Therefore, \ is so meta-magic that it is not in META.
  1066.                  */
  1067.                 curchr = -1;
  1068.                 at_start = FALSE;            /* We still want to be able to say "/\*ptr" */
  1069.                 peekchr();
  1070.                 curchr ^= Magic(0);
  1071.             }
  1072.             else if (vim_strchr(REGEXP_ABBR, regparse[0]))
  1073.             {
  1074.                 /*
  1075.                  * Handle abbreviations, like "\t" for TAB -- webb
  1076.                  */
  1077.                 switch (regparse[0])
  1078.                 {
  1079.                     case 'r':    curchr = CR;        break;
  1080.                     case 't':    curchr = TAB;        break;
  1081.                     case 'e':    curchr = ESC;        break;
  1082.                     case 'b':    curchr = Ctrl('H');    break;
  1083.                 }
  1084.             }
  1085.             else
  1086.             {
  1087.                 /*
  1088.                  * Next character can never be (made) magic?
  1089.                  * Then backslashing it won't do anything.
  1090.                  */
  1091.                 curchr = regparse[0];
  1092.             }
  1093.             break;
  1094.         }
  1095.     }
  1096.  
  1097.     return curchr;
  1098. }
  1099.  
  1100. static void
  1101. skipchr()
  1102. {
  1103.     regparse++;
  1104.     at_start = FALSE;
  1105.     prevchr = curchr;
  1106.     curchr = nextchr;        /* use previously unget char, or -1 */
  1107.     nextchr = -1;
  1108. }
  1109.  
  1110. static int
  1111. getchr()
  1112. {
  1113.     int chr;
  1114.  
  1115.     chr = peekchr();
  1116.     skipchr();
  1117.  
  1118.     return chr;
  1119. }
  1120.  
  1121. /*
  1122.  * put character back. Works only once!
  1123.  */
  1124. static void
  1125. ungetchr()
  1126. {
  1127.     nextchr = curchr;
  1128.     curchr = prevchr;
  1129.     /*
  1130.      * Backup regparse as well; not because we will use what it points at,
  1131.      * but because skipchr() will bump it again.
  1132.      */
  1133.     regparse--;
  1134. }
  1135.  
  1136. /*
  1137.  * vim_regexec and friends
  1138.  */
  1139.  
  1140. /*
  1141.  * Global work variables for vim_regexec().
  1142.  */
  1143. static char_u    *reginput;        /* String-input pointer. */
  1144. static char_u    *regbol;         /* Beginning of input, for ^ check. */
  1145. static char_u   **regstartp;        /* Pointer to startp array. */
  1146. /* static char_u   **regendp;    */    /* Ditto for endp. */
  1147.  
  1148. /*
  1149.  * Forwards.
  1150.  */
  1151. static int        regtry __ARGS((regexp *, char_u *));
  1152. static int        regmatch __ARGS((char_u *));
  1153. static int        regrepeat __ARGS((char_u *));
  1154.  
  1155. #ifdef DEBUG
  1156. int             regnarrate = 1;
  1157. void            regdump __ARGS((regexp *));
  1158. static char_u    *regprop __ARGS((char_u *));
  1159. #endif
  1160.  
  1161. /*
  1162.  * vim_regexec - match a regexp against a string
  1163.  * Return non-zero if there is a match.
  1164.  */
  1165. int
  1166. vim_regexec(prog, string, at_bol)
  1167.     register regexp *prog;
  1168.     register char_u  *string;
  1169.     int             at_bol;
  1170. {
  1171.     register char_u  *s;
  1172.  
  1173.     /* Be paranoid... */
  1174.     if (prog == NULL || string == NULL) {
  1175.         emsg(e_null);
  1176.         rc_did_emsg = TRUE;
  1177.         return 0;
  1178.     }
  1179.     /* Check validity of program. */
  1180.     if (UCHARAT(prog->program) != MAGIC) {
  1181.         emsg(e_re_corr);
  1182.         rc_did_emsg = TRUE;
  1183.         return 0;
  1184.     }
  1185.     /* If there is a "must appear" string, look for it. */
  1186.     if (prog->regmust != NULL) {
  1187.         s = string;
  1188.         while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
  1189.             if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
  1190.                 break;            /* Found it. */
  1191.             s++;
  1192.         }
  1193.         if (s == NULL)            /* Not present. */
  1194.             return 0;
  1195.     }
  1196.     /* Mark beginning of line for ^ . */
  1197.     if (at_bol)
  1198.         regbol = string;        /* is possible to match bol */
  1199.     else
  1200.         regbol = NULL;            /* we aren't there, so don't match it */
  1201.  
  1202.     /* Simplest case:  anchored match need be tried only once. */
  1203.     if (prog->reganch)
  1204.         return regtry(prog, string);
  1205.  
  1206.     /* Messy cases:  unanchored match. */
  1207.     s = string;
  1208.     if (prog->regstart != '\0')
  1209.         /* We know what char it must start with. */
  1210.         while ((s = cstrchr(s, prog->regstart)) != NULL) {
  1211.             if (regtry(prog, s))
  1212.                 return 1;
  1213.             s++;
  1214.         }
  1215.     else
  1216.         /* We don't -- general case. */
  1217.         do {
  1218.             if (regtry(prog, s))
  1219.                 return 1;
  1220.         } while (*s++ != '\0');
  1221.  
  1222.     /* Failure. */
  1223.     return 0;
  1224. }
  1225.  
  1226. /*
  1227.  - regtry - try match at specific point
  1228.  */
  1229. static int                        /* 0 failure, 1 success */
  1230. regtry(prog, string)
  1231.     regexp           *prog;
  1232.     char_u           *string;
  1233. {
  1234.     register int    i;
  1235.     register char_u **sp;
  1236.     register char_u **ep;
  1237.  
  1238.     reginput = string;
  1239.     regstartp = prog->startp;
  1240.     regendp = prog->endp;
  1241.  
  1242.     sp = prog->startp;
  1243.     ep = prog->endp;
  1244.     for (i = NSUBEXP; i > 0; i--) {
  1245.         *sp++ = NULL;
  1246.         *ep++ = NULL;
  1247.     }
  1248.     if (regmatch(prog->program + 1)) {
  1249.         prog->startp[0] = string;
  1250.         prog->endp[0] = reginput;
  1251.         return 1;
  1252.     } else
  1253.         return 0;
  1254. }
  1255.  
  1256. /*
  1257.  - regmatch - main matching routine
  1258.  *
  1259.  * Conceptually the strategy is simple:  check to see whether the current
  1260.  * node matches, call self recursively to see whether the rest matches,
  1261.  * and then act accordingly.  In practice we make some effort to avoid
  1262.  * recursion, in particular by going through "ordinary" nodes (that don't
  1263.  * need to know whether the rest of the match failed) by a loop instead of
  1264.  * by recursion.
  1265.  */
  1266. static int                        /* 0 failure, 1 success */
  1267. regmatch(prog)
  1268.     char_u           *prog;
  1269. {
  1270.     register char_u  *scan;        /* Current node. */
  1271.     char_u           *next;        /* Next node. */
  1272.  
  1273.     scan = prog;
  1274. #ifdef DEBUG
  1275.     if (scan != NULL && regnarrate)
  1276.         fprintf(stderr, "%s(\n", regprop(scan));
  1277. #endif
  1278.     while (scan != NULL) {
  1279. #ifdef DEBUG
  1280.         if (regnarrate) {
  1281.             fprintf(stderr, "%s...\n", regprop(scan));
  1282.         }
  1283. #endif
  1284.         next = regnext(scan);
  1285.         switch (OP(scan)) {
  1286.           case BOL:
  1287.             if (reginput != regbol)
  1288.                 return 0;
  1289.             break;
  1290.           case EOL:
  1291.             if (*reginput != '\0')
  1292.                 return 0;
  1293.             break;
  1294.           case BOW:        /* \<word; reginput points to w */
  1295.               if (reginput != regbol && iswordchar(reginput[-1]))
  1296.                 return 0;
  1297.               if (!reginput[0] || !iswordchar(reginput[0]))
  1298.                 return 0;
  1299.             break;
  1300.           case EOW:        /* word\>; reginput points after d */
  1301.               if (reginput == regbol || !iswordchar(reginput[-1]))
  1302.                 return 0;
  1303.               if (reginput[0] && iswordchar(reginput[0]))
  1304.                 return 0;
  1305.             break;
  1306.           case ANY:
  1307.             if (*reginput == '\0')
  1308.                 return 0;
  1309.             reginput++;
  1310.             break;
  1311.           case IDENT:
  1312.               if (!isidchar(*reginput))
  1313.                 return 0;
  1314.             reginput++;
  1315.             break;
  1316.           case WORD:
  1317.               if (!iswordchar(*reginput))
  1318.                 return 0;
  1319.             reginput++;
  1320.             break;
  1321.           case FNAME:
  1322.               if (!isfilechar(*reginput))
  1323.                 return 0;
  1324.             reginput++;
  1325.             break;
  1326.           case PRINT:
  1327.               if (charsize(*reginput) != 1)
  1328.                 return 0;
  1329.             reginput++;
  1330.             break;
  1331.           case SIDENT:
  1332.               if (isdigit(*reginput) || !isidchar(*reginput))
  1333.                 return 0;
  1334.             reginput++;
  1335.             break;
  1336.           case SWORD:
  1337.               if (isdigit(*reginput) || !iswordchar(*reginput))
  1338.                 return 0;
  1339.             reginput++;
  1340.             break;
  1341.           case SFNAME:
  1342.               if (isdigit(*reginput) || !isfilechar(*reginput))
  1343.                 return 0;
  1344.             reginput++;
  1345.             break;
  1346.           case SPRINT:
  1347.               if (isdigit(*reginput) || charsize(*reginput) != 1)
  1348.                 return 0;
  1349.             reginput++;
  1350.             break;
  1351.           case EXACTLY:{
  1352.                 register int    len;
  1353.                 register char_u  *opnd;
  1354.  
  1355.                 opnd = OPERAND(scan);
  1356.                 /* Inline the first character, for speed. */
  1357.                 if (*opnd != *reginput && (!reg_ic || TO_UPPER(*opnd) != TO_UPPER(*reginput)))
  1358.                     return 0;
  1359.                 len = STRLEN(opnd);
  1360.                 if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
  1361.                     return 0;
  1362.                 reginput += len;
  1363.             }
  1364.             break;
  1365.           case ANYOF:
  1366.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
  1367.                 return 0;
  1368.             reginput++;
  1369.             break;
  1370.           case ANYBUT:
  1371.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
  1372.                 return 0;
  1373.             reginput++;
  1374.             break;
  1375.           case NOTHING:
  1376.             break;
  1377.           case BACK:
  1378.             break;
  1379.           case MOPEN + 1:
  1380.           case MOPEN + 2:
  1381.           case MOPEN + 3:
  1382.           case MOPEN + 4:
  1383.           case MOPEN + 5:
  1384.           case MOPEN + 6:
  1385.           case MOPEN + 7:
  1386.           case MOPEN + 8:
  1387.           case MOPEN + 9:{
  1388.                 register int    no;
  1389.                 register char_u  *save;
  1390.  
  1391.                 no = OP(scan) - MOPEN;
  1392.                 save = regstartp[no];
  1393.                 regstartp[no] = reginput; /* Tentatively */
  1394. #ifdef DEBUG
  1395.                 printf("MOPEN  %d pre  @'%s' ('%s' )'%s'\n",
  1396.                     no, save,
  1397.                     regstartp[no] ? regstartp[no] : "NULL",
  1398.                     regendp[no] ? regendp[no] : "NULL");
  1399. #endif
  1400.  
  1401.                 if (regmatch(next)) {
  1402. #ifdef DEBUG
  1403.                 printf("MOPEN  %d post @'%s' ('%s' )'%s'\n",
  1404.                     no, save,
  1405.                     regstartp[no] ? regstartp[no] : "NULL",
  1406.                     regendp[no] ? regendp[no] : "NULL");
  1407. #endif
  1408.                     return 1;
  1409.                 }
  1410.                 regstartp[no] = save;        /* We were wrong... */
  1411.                 return 0;
  1412.             }
  1413.             /* break; Not Reached */
  1414.           case MCLOSE + 1:
  1415.           case MCLOSE + 2:
  1416.           case MCLOSE + 3:
  1417.           case MCLOSE + 4:
  1418.           case MCLOSE + 5:
  1419.           case MCLOSE + 6:
  1420.           case MCLOSE + 7:
  1421.           case MCLOSE + 8:
  1422.           case MCLOSE + 9:{
  1423.                 register int    no;
  1424.                 register char_u  *save;
  1425.  
  1426.                 no = OP(scan) - MCLOSE;
  1427.                 save = regendp[no];
  1428.                 regendp[no] = reginput; /* Tentatively */
  1429. #ifdef DEBUG
  1430.                 printf("MCLOSE %d pre  @'%s' ('%s' )'%s'\n",
  1431.                     no, save,
  1432.                     regstartp[no] ? regstartp[no] : "NULL",
  1433.                     regendp[no] ? regendp[no] : "NULL");
  1434. #endif
  1435.  
  1436.                 if (regmatch(next)) {
  1437. #ifdef DEBUG
  1438.                 printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
  1439.                     no, save,
  1440.                     regstartp[no] ? regstartp[no] : "NULL",
  1441.                     regendp[no] ? regendp[no] : "NULL");
  1442. #endif
  1443.                     return 1;
  1444.                 }
  1445.                 regendp[no] = save;        /* We were wrong... */
  1446.                 return 0;
  1447.             }
  1448.             /* break; Not Reached */
  1449. #ifdef BACKREF
  1450.           case BACKREF + 1:
  1451.           case BACKREF + 2:
  1452.           case BACKREF + 3:
  1453.           case BACKREF + 4:
  1454.           case BACKREF + 5:
  1455.           case BACKREF + 6:
  1456.           case BACKREF + 7:
  1457.           case BACKREF + 8:
  1458.           case BACKREF + 9:{
  1459.                 register int    no;
  1460.                 int                len;
  1461.  
  1462.                 no = OP(scan) - BACKREF;
  1463.                 if (regendp[no] != NULL) {
  1464.                     len = (int)(regendp[no] - regstartp[no]);
  1465.                     if (cstrncmp(regstartp[no], reginput, len) != 0)
  1466.                         return 0;
  1467.                     reginput += len;
  1468.                 } else {
  1469.                     /*emsg("backref to 0-repeat");*/
  1470.                     /*return 0;*/
  1471.                 }
  1472.               }
  1473.             break;
  1474. #endif
  1475.           case BRANCH:{
  1476.                 register char_u  *save;
  1477.  
  1478.                 if (OP(next) != BRANCH) /* No choice. */
  1479.                     next = OPERAND(scan);        /* Avoid recursion. */
  1480.                 else {
  1481.                     do {
  1482.                         save = reginput;
  1483.                         if (regmatch(OPERAND(scan)))
  1484.                             return 1;
  1485.                         reginput = save;
  1486.                         scan = regnext(scan);
  1487.                     } while (scan != NULL && OP(scan) == BRANCH);
  1488.                     return 0;
  1489.                     /* NOTREACHED */
  1490.                 }
  1491.             }
  1492.             break;
  1493.           case STAR:
  1494.           case PLUS:{
  1495.                 register int    nextch;
  1496.                 register int    no;
  1497.                 register char_u  *save;
  1498.                 register int    min;
  1499.  
  1500.                 /*
  1501.                  * Lookahead to avoid useless match attempts when we know
  1502.                  * what character comes next.
  1503.                  */
  1504.                 nextch = '\0';
  1505.                 if (OP(next) == EXACTLY)
  1506.                 {
  1507.                     nextch = *OPERAND(next);
  1508.                     if (reg_ic)
  1509.                         nextch = TO_UPPER(nextch);
  1510.                 }
  1511.                 min = (OP(scan) == STAR) ? 0 : 1;
  1512.                 save = reginput;
  1513.                 no = regrepeat(OPERAND(scan));
  1514.                 while (no >= min)
  1515.                 {
  1516.                     /* If it could work, try it. */
  1517.                     if (nextch == '\0' || (*reginput == nextch ||
  1518.                                     (reg_ic && TO_UPPER(*reginput) == nextch)))
  1519.                         if (regmatch(next))
  1520.                             return 1;
  1521.                     /* Couldn't or didn't -- back up. */
  1522.                     no--;
  1523.                     reginput = save + no;
  1524.                 }
  1525.                 return 0;
  1526.             }
  1527.             /* break; Not Reached */
  1528.           case END:
  1529.             return 1;         /* Success! */
  1530.             /* break; Not Reached */
  1531.           default:
  1532.             emsg(e_re_corr);
  1533.             return 0;
  1534.             /* break; Not Reached */
  1535.         }
  1536.  
  1537.         scan = next;
  1538.     }
  1539.  
  1540.     /*
  1541.      * We get here only if there's trouble -- normally "case END" is the
  1542.      * terminating point.
  1543.      */
  1544.     emsg(e_re_corr);
  1545.     return 0;
  1546. }
  1547.  
  1548. /*
  1549.  - regrepeat - repeatedly match something simple, report how many
  1550.  */
  1551. static int
  1552. regrepeat(p)
  1553.     char_u           *p;
  1554. {
  1555.     register int    count = 0;
  1556.     register char_u  *scan;
  1557.     register char_u  *opnd;
  1558.  
  1559.     scan = reginput;
  1560.     opnd = OPERAND(p);
  1561.     switch (OP(p)) {
  1562.       case ANY:
  1563.         count = STRLEN(scan);
  1564.         scan += count;
  1565.         break;
  1566.       case IDENT:
  1567.         for (count = 0; isidchar(*scan); ++count)
  1568.             ++scan;
  1569.         break;
  1570.       case WORD:
  1571.         for (count = 0; iswordchar(*scan); ++count)
  1572.             ++scan;
  1573.         break;
  1574.       case FNAME:
  1575.         for (count = 0; isfilechar(*scan); ++count)
  1576.             ++scan;
  1577.         break;
  1578.       case PRINT:
  1579.         for (count = 0; charsize(*scan) == 1; ++count)
  1580.             ++scan;
  1581.         break;
  1582.       case SIDENT:
  1583.         for (count = 0; !isdigit(*scan) && isidchar(*scan); ++count)
  1584.             ++scan;
  1585.         break;
  1586.       case SWORD:
  1587.         for (count = 0; !isdigit(*scan) && iswordchar(*scan); ++count)
  1588.             ++scan;
  1589.         break;
  1590.       case SFNAME:
  1591.         for (count = 0; !isdigit(*scan) && isfilechar(*scan); ++count)
  1592.             ++scan;
  1593.         break;
  1594.       case SPRINT:
  1595.         for (count = 0; !isdigit(*scan) && charsize(*scan) == 1; ++count)
  1596.             ++scan;
  1597.         break;
  1598.       case EXACTLY:
  1599.         while (*opnd == *scan || (reg_ic && TO_UPPER(*opnd) == TO_UPPER(*scan)))
  1600.         {
  1601.             count++;
  1602.             scan++;
  1603.         }
  1604.         break;
  1605.       case ANYOF:
  1606.         while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
  1607.         {
  1608.             count++;
  1609.             scan++;
  1610.         }
  1611.         break;
  1612.       case ANYBUT:
  1613.         while (*scan != '\0' && cstrchr(opnd, *scan) == NULL) {
  1614.             count++;
  1615.             scan++;
  1616.         }
  1617.         break;
  1618.       default:                    /* Oh dear.  Called inappropriately. */
  1619.         emsg(e_re_corr);
  1620.         count = 0;                /* Best compromise. */
  1621.         break;
  1622.     }
  1623.     reginput = scan;
  1624.  
  1625.     return count;
  1626. }
  1627.  
  1628. /*
  1629.  - regnext - dig the "next" pointer out of a node
  1630.  */
  1631. static char_u    *
  1632. regnext(p)
  1633.     register char_u  *p;
  1634. {
  1635.     register int    offset;
  1636.  
  1637.     if (p == ®dummy)
  1638.         return NULL;
  1639.  
  1640.     offset = NEXT(p);
  1641.     if (offset == 0)
  1642.         return NULL;
  1643.  
  1644.     if (OP(p) == BACK)
  1645.         return p - offset;
  1646.     else
  1647.         return p + offset;
  1648. }
  1649.  
  1650. #ifdef DEBUG
  1651.  
  1652. /*
  1653.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1654.  */
  1655. void
  1656. regdump(r)
  1657.     regexp           *r;
  1658. {
  1659.     register char_u  *s;
  1660.     register int    op = EXACTLY;        /* Arbitrary non-END op. */
  1661.     register char_u  *next;
  1662.  
  1663.  
  1664.     s = r->program + 1;
  1665.     while (op != END) {         /* While that wasn't END last time... */
  1666.         op = OP(s);
  1667.         printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1668.         next = regnext(s);
  1669.         if (next == NULL)        /* Next ptr. */
  1670.             printf("(0)");
  1671.         else
  1672.             printf("(%d)", (s - r->program) + (next - s));
  1673.         s += 3;
  1674.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1675.             /* Literal string, where present. */
  1676.             while (*s != '\0') {
  1677.                 putchar(*s);
  1678.                 s++;
  1679.             }
  1680.             s++;
  1681.         }
  1682.         putchar('\n');
  1683.     }
  1684.  
  1685.     /* Header fields of interest. */
  1686.     if (r->regstart != '\0')
  1687.         printf("start `%c' ", r->regstart);
  1688.     if (r->reganch)
  1689.         printf("anchored ");
  1690.     if (r->regmust != NULL)
  1691.         printf("must have \"%s\"", r->regmust);
  1692.     printf("\n");
  1693. }
  1694.  
  1695. /*
  1696.  - regprop - printable representation of opcode
  1697.  */
  1698. static char_u    *
  1699. regprop(op)
  1700.     char_u           *op;
  1701. {
  1702.     register char_u  *p;
  1703.     static char_u     buf[50];
  1704.  
  1705.     (void) strcpy(buf, ":");
  1706.  
  1707.     switch (OP(op)) {
  1708.       case BOL:
  1709.         p = "BOL";
  1710.         break;
  1711.       case EOL:
  1712.         p = "EOL";
  1713.         break;
  1714.       case ANY:
  1715.         p = "ANY";
  1716.         break;
  1717.       case IDENT:
  1718.           p = "IDENT";
  1719.         break;
  1720.       case WORD:
  1721.           p = "WORD";
  1722.         break;
  1723.       case FNAME:
  1724.           p = "FNAME";
  1725.         break;
  1726.       case PRINT:
  1727.           p = "PRINT";
  1728.         break;
  1729.       case SIDENT:
  1730.           p = "SIDENT";
  1731.         break;
  1732.       case SWORD:
  1733.           p = "SWORD";
  1734.         break;
  1735.       case SFNAME:
  1736.           p = "SFNAME";
  1737.         break;
  1738.       case SPRINT:
  1739.           p = "SPRINT";
  1740.         break;
  1741.       case ANYOF:
  1742.         p = "ANYOF";
  1743.         break;
  1744.       case ANYBUT:
  1745.         p = "ANYBUT";
  1746.         break;
  1747.       case BRANCH:
  1748.         p = "BRANCH";
  1749.         break;
  1750.       case EXACTLY:
  1751.         p = "EXACTLY";
  1752.         break;
  1753.       case NOTHING:
  1754.         p = "NOTHING";
  1755.         break;
  1756.       case BACK:
  1757.         p = "BACK";
  1758.         break;
  1759.       case END:
  1760.         p = "END";
  1761.         break;
  1762.       case MOPEN + 1:
  1763.       case MOPEN + 2:
  1764.       case MOPEN + 3:
  1765.       case MOPEN + 4:
  1766.       case MOPEN + 5:
  1767.       case MOPEN + 6:
  1768.       case MOPEN + 7:
  1769.       case MOPEN + 8:
  1770.       case MOPEN + 9:
  1771.         sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
  1772.         p = NULL;
  1773.         break;
  1774.       case MCLOSE + 1:
  1775.       case MCLOSE + 2:
  1776.       case MCLOSE + 3:
  1777.       case MCLOSE + 4:
  1778.       case MCLOSE + 5:
  1779.       case MCLOSE + 6:
  1780.       case MCLOSE + 7:
  1781.       case MCLOSE + 8:
  1782.       case MCLOSE + 9:
  1783.         sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
  1784.         p = NULL;
  1785.         break;
  1786.       case BACKREF + 1:
  1787.       case BACKREF + 2:
  1788.       case BACKREF + 3:
  1789.       case BACKREF + 4:
  1790.       case BACKREF + 5:
  1791.       case BACKREF + 6:
  1792.       case BACKREF + 7:
  1793.       case BACKREF + 8:
  1794.       case BACKREF + 9:
  1795.         sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
  1796.         p = NULL;
  1797.         break;
  1798.       case STAR:
  1799.         p = "STAR";
  1800.         break;
  1801.       case PLUS:
  1802.         p = "PLUS";
  1803.         break;
  1804.       default:
  1805.         sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
  1806.         p = NULL;
  1807.         break;
  1808.     }
  1809.     if (p != NULL)
  1810.         (void) strcat(buf, p);
  1811.     return buf;
  1812. }
  1813. #endif
  1814.  
  1815. /*
  1816.  * The following is provided for those people who do not have strcspn() in
  1817.  * their C libraries.  They should get off their butts and do something
  1818.  * about it; at least one public-domain implementation of those (highly
  1819.  * useful) string routines has been published on Usenet.
  1820.  */
  1821. #ifndef HAVE_STRCSPN
  1822. /*
  1823.  * strcspn - find length of initial segment of s1 consisting entirely
  1824.  * of characters not from s2
  1825.  */
  1826.  
  1827.     static size_t
  1828. strcspn(s1, s2)
  1829.     const char_u           *s1;
  1830.     const char_u           *s2;
  1831. {
  1832.     register char_u  *scan1;
  1833.     register char_u  *scan2;
  1834.     register int    count;
  1835.  
  1836.     count = 0;
  1837.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1838.         for (scan2 = s2; *scan2 != '\0';)        /* ++ moved down. */
  1839.             if (*scan1 == *scan2++)
  1840.                 return count;
  1841.         count++;
  1842.     }
  1843.     return count;
  1844. }
  1845. #endif
  1846.  
  1847. /*
  1848.  * Compare two strings, ignore case if reg_ic set.
  1849.  * Return 0 if strings match, non-zero otherwise.
  1850.  */
  1851.     int
  1852. cstrncmp(s1, s2, n)
  1853.     char_u           *s1, *s2;
  1854.     int             n;
  1855. {
  1856.     if (!reg_ic)
  1857.         return STRNCMP(s1, s2, (size_t)n);
  1858.  
  1859.     return vim_strnicmp(s1, s2, (size_t)n);
  1860. }
  1861.  
  1862. /*
  1863.  * cstrchr: This function is used a lot for simple searches, keep it fast!
  1864.  */
  1865.     static char_u *
  1866. cstrchr(s, c)
  1867.     char_u           *s;
  1868.     register int    c;
  1869. {
  1870.     register char_u           *p;
  1871.  
  1872.     if (!reg_ic)
  1873.         return vim_strchr(s, c);
  1874.  
  1875.     c = TO_UPPER(c);
  1876.  
  1877.     for (p = s; *p; p++)
  1878.     {
  1879.         if (TO_UPPER(*p) == c)
  1880.             return p;
  1881.     }
  1882.     return NULL;
  1883. }
  1884.